Sen(Qian)’s Memo

https://arxiv.org/abs/1809.03207

Elkan Notoらが定式化したsingle-training-setでは、明確に$Pr(s = 1)$がわかるものだった。そしてここではSCAR仮定を使っている=完全にランダムに選択する。この仮定の下では、$Pr(s = +1 | \mathbf{x}, y = +1) = Pr(s = +1 | y)$が成り立つ。しかし現実ではそうはうまく行かない。

この論文では、SCARではなく、より弱いSAR、Selected At Randomという仮説を提言している。データ$\mathbf{x}$の一部の成分を引数に受け取って計算される関数によって、選ばれる確率が求まる。
因果推論(casual inference literature)で使われる、傾向スコア(propensity score)をPU Learningにも持ち込む。

なお、Preliminariesでは、サーベイ論文における4つの仮定の参考文献をそれぞれ引用している。

$\mathbf{x}$がデータで、ラベルがついているならば$y=+1$ついてなければ$y=-1$である。そして、Positiveとラベル付けされているときは$s=+1$そうじゃないときは$s=0$である。$y=-1$のサンプルが$s=+1$となることはない。

Elkan, Notoらの論文にもあるように、PU LearningのSCARの着想は、データが欠損しているときの条件から来ていた。これを援用して定義してみる。

• SCAR　Selected Completely At Random。Positive例ならば一定確率で選ぶ。データ$\mathbf{x}$によっても、Positiveである確率$Pr(y = +1 | \mathbf{x})$にも依存しない。
• SAR　Selected At Random。 データ$\mathbf{x}$を引数に取る関数$e$があり、その関数の出力値がラベル付けされる確率。
  $e(\mathbf{x}) = Pr(s=+1|\mathbf{x})$

  しかし、この確率は$Pr(y = +1 | \mathbf{x})$には依存しない。一例として、Ground-TruthがPositiveっぽい(っぽくない)からといって、ラベルがつく確率はそれに依存して変わることはない(あくまで$\mathbf{x}$にのみ依存する)。

• SNAR　Selected Not At Random. 上の2ケース以外。さすがに一概に論じることができない。

$s=+1$のサンプルが少ないのは根本的な問題となる。少ないのは、サンプル頻度が少ないか、そもそもが少ないか。多くの提案されている仮定は基本的にサンプル頻度が少ないことに帰している。

傾向スコアのやり方を参考にしている。

こちらのQiita記事を大いに参考にした。

共変量とは、因と果の両方に依存されてる変量のこと。これらを想定しないと偽相関を見抜けない。グラフィカルモデルでいうと以下のようになる。

共変量 ----> 因
|         /
|       /
|    /
|  /
v v
果

比較する2つグループで、そもそも共変量が絡んで、キレイにバイアスなしの状態に分けられていないことが多い。(例として、高血圧の人が多く投薬群、正常な人の多くがプラセボ群に入ってしまうとか)。そもそも全てのステータスが完全に同じ2人を見つけるなど理論上はあり得ない。

そこで、人iが介入される(上で言う投薬群)確率を傾向スコアとして定義する。そして、傾向スコアを参考にして2つの群に割り振りをすればいい。割り振り方としては近いペアをランダムに入れるetcなどがある。具体的な定義は以下の通り。

$Z _i$を1ならば介入あり、0なら介入なしとして、以下のものが傾向スコア。つまり、共変量を条件とした$Z _i = 1$の条件付確率である。

具体的には、いかにしてpropensity score$e(\mathbf{x} _i)$の計算をするかは決まっていない。簡単なものは対次元ロジスティック回帰、もっと表現力を上げるならばNNなど。

この論文で使われるのは、IPW(Inverse-Propensity-Weighting)という割り当て手法。
考え方としては、群への割り当て自体は適当でいい。しかし、これのバイアスをうまく除去したい。そこで、該当の全てに対して、できるだけ全てが平等に現れてほしい。そのためには出現頻度が高いものの重みを小さく、低いものの重みを大きくしたい。これにより、「ランダムに選んでいるように見せかける」ことができ、そこから$\mathbb{E} [A _{t}] - \mathbb{E} [A _{ut}]$の値を計算できる。$A_t$は処置あり、$A_{ut}$は処置なし。

前半では$Z _i = 1$、後半では$Z _i = 0$だけ集めており、前半では$e(\mathbf{x} _i)$の逆数だが、後半の群は介入なしなので、$1 - e(\mathbf{x} _i)$の逆数を使う。propensity scoreは$Pr(Z_i=1|\mathbf{x}_i)$なので、確率的に余事象として引き算すればいい。これによって、平均処置効果ATEという、バイアスを排した2つのグループの間の平均の差を得られる。

2つの式があるが、下の方がより分散が小さくなる。また、いずれの式でも$N \to \infty$とすれば、真の値へと収束することが保証されている。

とすると、共変量$\mathbf{x}, y$のもとでのラベルが付く確率を傾向スコアとみなせる。

先ほどのIPWをそのまま使えるならば、一番幸せであるが、ここではNegative例が1つのもないため、$1 - e(\mathbf{x} _i) = p(s = 0 | y, \mathbf{x})$のyの情報がないためそのままでは使えない。

各例の傾向スコアが$e(\mathbf{x} _i)$とすると、$s=+1$のラベル付きサンプルを$\frac{1}{e(\mathbf{x} _i)}$の重みをもつPositive例と、$1 - \frac{1}{e(\mathbf{x} _i)}$のNegative例として分けて扱うことができると、因果推論の知識で分かった。ということで早速$s=+1$のサンプルを同様に分解していく、というモチベになる。

分けて扱うといっても、📄2015-ICML-[uPU] Convex Formulation for Learning from Positive and Unlabeled Data でも$R(g)=\pi \mathbb{E}_1 [l(g(X)) - l(-g(X))] + \mathbb{E}_X [l(-g(X))]$となっており、$s=+1$の例を$\pi$の重みをもつPositive例と、$-\pi$の重みをもつNegative例として扱っている。しかし、今回はUnlabeledのデータについてそれぞれ重みをつけていくという点で、📄2008-KDD-Learning Classifiers from Only Positive and Unlabeled Data と似ている。

真の傾向スコアを知っている、知らないで2通りの設定を考える。

どれほどずれているのかの評価を次のように行える。(ここの経験的な式への変形あってる？)

損失関数としては、1乗誤差、2乗誤差、対数誤差$l(y=1, \hat{y}) = - \log \hat{y}, l(y=1, \hat{y}) = - \log (1 - \hat{y})$がある。

そして、$s _i = e _i y _i$という等式が成り立つ。これはなぜ成り立つか。以下のようなものである。

• $s _i, y _i$は具体的な値であるので、経験分布であると考える。両辺を$n$で割る。$s _i / n = e _i y _i / n$
  • 経験分布とは、具体的な試行から得られる分布。もし試行で現れてない例では0、現れてるものは$n$回の試行では1回現れるごとに$1 / n$という確率となる=最尤推定。
• $s _i$は$\hat{p}(\mathbf{x} _i, s _i = +1)$というかたちで経験分布に現れる。(分布から確率を計算する時は具体的な値を引数に渡すので)
  • $s _i / n$に関して、$s _i = 0, 1$である。今回は$s _i = 1$という条件で考えるが、$s _i = 1$が成り立つ時は$1 / n、s _i = 0$が成り立つときは$0 / n = 0$である。よって、$s _i / n = \hat{p}(\mathbf{x} _i, s _i = +1)$
  • このように、本来は(経験)分布の中に、変数に入れることができる。このように経験的な式を、該当する経験分布に書き換えることによって、経験じゃない分布でも成り立つことから、ベイズの定理を適用できる。非常に有用なテク。
• $s _i$の時と同様に、$y _i$についても、$\hat{p}(\mathbf{x} _i, y _i = +1)$という経験分布について$y _i = +1$であれば$1/n$、そうでなければ$0/n$により、同様に$y _i / n = \hat{p}(\mathbf{x} _i, y _i)$と、分布に書き直せる。
• 書き直したのちは、以下のように経験分布の$\hat{p}$は試行を無限回にすることで、$p$に近づけられる。これを利用して式変形する。

なお、SCARの仮定では$\forall e _i = \mathrm{const}$であるので、下式の最小化の式変形は不要である。📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data ではSCARという仮定を前提としてここを飛ばして、cost-sensitiveの式変形へとつないだ。

それを踏まえると、$s _i = e _i y _i$としても、正しい答えへと収束するとわかる。これを代入すると、最終的に最小化をしたいのは、以下の二値分類とみなした時の式。

本来$y_i = 0, 1$なので片方の項しか残らないが、$s_i = e_i y_i$を使うことで、小数点になっていくのが面白いところ。

この式では

• $y _i$と$1 - y _i$のPN Learningの式から、$s _i$だけを使った式にしたい。
  • モチベとして$s _i$と$1 - s _i$のかたちにしてみるとどうなるか？($s _i$しか知らないので、$y _i$のようなかたちにしたい。)
  • 既存の📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data ではSCARなのでこれを行わず、$\pi = p(y = +1)$を使うかたちで変形をし、この手法は行わなかった。
  • SCARであれば、$e _i$は定数であるので$s _i$と$y _i$を簡単に定数倍でよかった。
• Positive例であれば、バイアスを考慮したPropensity Scoreによって、PositiveとNegativeに分解できるというのを使う。
  • この形を作るために式変形をし、分母に出てきた$e(\mathbf{x}_i)$を消すために分母にまた同じものを乗じ、それの帳尻合わせを$(1-e(\mathbf{x}_i) y_i) l_{y=0}(\hat{y}_i)$の部分で行っている。
• 変形後の式ではUnlabeledの$\mathbf{x} _i$では、$y = 0$とみなした時の損失で評価する(cost-sensitive特有のnegativeに偏る問題はここでもある)
• 式変形の結果論として以下のことが言える。
  • Labeled(Positiveの一部)の$\mathbf{x} _i$では、重みが$1 / e _i$のPositiveとしての損失と、$(1 / e _i) - 1$のNegativeとしての損失を持つ。
  • Unlabeledの$\mathbf{x}$では、重みが$1 - y _i e _i$のNegativeとしてとして扱う。

McDiarmidの不等式で評価していた。省略

傾向スコアの推定を行うしかない。推定したのが$\hat{e _i}$としたとき、真のリスク関数との差の上界？は以下のようになる。

ここからわかることとして、

• $\hat{e _i}, e _i$が完全に一致すれば0になる。
• $l _{y = 1}(\hat{y} _i) = l _{y = 0}(\hat{y} _i)$でも成り立つが、これは非現実的では？
• Positiveの傾向スコアの正確性のみが影響する。
• 傾向スコアが間違っているとき、予測したクラス$\hat{y _i}$が0か1かに近い、自信満々であるほど大きく響く。
• 傾向スコアが小さいとき、マイナスに式は行くし絶対値は大きくなる。

予測するときに、任意のデータが無規則にpropensityスコアを取るのは本質的には予測できない。依って、追加の仮定が必要であり、それの一例として、「$\mathbf{x}$のうちの一部の成分によるベクトル$\mathbf{x} _e$を選び、それだけでpropensity scoreの算出をする」。

複数の層にデータが分けられ、その層の中では各データはSCARであるとするならば、既存の手法で学習することはできる。しかし、これは連続値が$\mathbf{x} _e$に入る場合は使えないし、離散値だとしても指数関数的に層が増えてしまうので非現実的ではある。$\mathbf{x} _e$の次元は低い方が望ましい。

📄EM Algorithmの解説 。$q, \theta$などの記号はこの中に準拠する。

データ$\mathbf{x} _i$、ラベルがついている$s _i$、$\hat{f}$を分類器、$\hat{e}$を傾向スコアの出力する関数モデルとする。
今回は$p(\mathbf{X}, \mathbf{y}, \mathbf{s} | f, e)$である(複数個であることを考えて$\mathbf{x}$を複数個組み合わせて行列$\mathbf{X}$とした。他も同様)。与えられたデータ$\mathbf{X}, \mathbf{y}, \mathbf{s}$を生成する事後分布の確率を最大化するように、$f, e$をパラメタとみなして最適化を行う。

EMアルゴリズムの定義より、隠れ変数$\mathbf{Z}$を用いて、変分下限$\mathcal{L}(q, \theta) = \mathbb{E} _{q(\mathbf{Z})} [ \frac{p(\mathbf{X}, \mathbf{s} | f, e)}{q(\mathbf{Z})} ]$を記述できる。

そして、EMアルゴリズムの設計通り、

• 今回は、隠れ変数$\mathbf{Z}$は$\mathbf{X}$のground truthのラベル$\mathbf{y}$とする。
• Eステップでは、$q(\mathbf{y}) = p(\mathbf{y} | \mathbf{X}, \mathbf{s}, f, e)$と代入する。$f$と$e$はoldとなる。
• Mステップでは、以下のような値を、$f, e$を動かして最大化する。

これを繰り返す。

まずは、隠れ変数$\mathbf{y}$の事後分布である$p(\mathbf{y} | \mathbf{X}, \mathbf{s}, f, e)$を求める。

• ラベル付きの時は$s _i = +1$であるため、必ずpositiveである。
• ラベルなしの場合、以下のように式変形を考えると成り立つとわかる。
  • わかるのは、理想的な訓練の結果として$f(\mathbf{x}) = p(y = +1 | \mathbf{x})$となり、$e(\mathbf{x}) = p(s = +1 | \mathbf{x})$となること。
  • この2つを利用して、$p(y = +1 | s = +0, \mathbf{x})$を得たい。
  • $Pr(s = +1 | \mathbf{x})$は$Pr(y = +1 | \mathbf{x})$と条件付独立であることを利用する。

これらを利用して、上式は以下のように導出できる。

先ほど得た$q(\mathbf{y}) = p(\mathbf{y} | \mathbf{X}, \mathbf{s}, f, e)$については以下の式となる。

これをもって、Eステップの最大化は以下の式に対して行う。

対数尤度での最大化なので、本体の尤度$p(\mathbf{X}, \mathbf{s}, \mathbf{y} | f, e)$を最大化するようなf, eとは何かを考える。仮定より、傾向スコアは$Pr(s = +1 | \mathbf{x})$であり、$Pr(y = +1 | \mathbf{x})$には依存しないとなるので、それぞれ独立に最大化することを考えればよい。

$\mathbf{y}$については、

• $y _i = 1$とされたものでは、分類器$f(\mathbf{x} _i)$も1に近づくべき。これを対数をとったもので最適化。
• $y _i = 0$とされたものでは、分類器$f(\mathbf{x} _i)$も0に近づくべき。これを対数をとったもので最適化。

と設計されている。よって、以下の損失関数の最小化としてる。予測した隠れ変数の$\mathbf{y}$は下式では$\hat{y} _i$と記述されている。

同様に、傾向スコアの予測器も以下のように設計できる。

• $s _i = 1$とされたものでは、傾向スコア$e(\mathbf{x} _i)$も1に近づくべき。これを対数をとったもので最適化。
• $s _i = 0$とされたものでは、傾向スコア$e(\mathbf{x} _i)$も0に近づくべき。これを対数をとったもので最適化。

対数を取る事により、$(0, 1)$の値域が$(-\infty, 0)$となるので、大きなスケールに拡張されより最小化が重要になる。収束判定、傾向スコアと識別器の「両方」が収束したら終了とする。傾向スコアの変化は、最後のn回の傾向スコア予測での変化量の平均と考えてOK。